๐Ÿ‘ฉโ€๐Ÿ’ป 11559. Puyo Puyo

@Seongukbaek Posted March 02, 2022 ยท Updated March 02, 2022 ยท 6 min read

๋ฌธ์ œ

๋ฟŒ์š”๋ฟŒ์š”์˜ ๋ฃฐ์€ ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค.

ํ•„๋“œ์— ์—ฌ๋Ÿฌ ๊ฐ€์ง€ ์ƒ‰๊น”์˜ ๋ฟŒ์š”๋ฅผ ๋†“๋Š”๋‹ค. ๋ฟŒ์š”๋Š” ์ค‘๋ ฅ์˜ ์˜ํ–ฅ์„ ๋ฐ›์•„ ์•„๋ž˜์— ๋ฐ”๋‹ฅ์ด๋‚˜ ๋‹ค๋ฅธ ๋ฟŒ์š”๊ฐ€ ๋‚˜์˜ฌ ๋•Œ๊นŒ์ง€ ์•„๋ž˜๋กœ ๋–จ์–ด์ง„๋‹ค. ๋ฟŒ์š”๋ฅผ ๋†“๊ณ  ๋‚œ ํ›„, ๊ฐ™์€ ์ƒ‰ ๋ฟŒ์š”๊ฐ€ 4๊ฐœ ์ด์ƒ ์ƒํ•˜์ขŒ์šฐ๋กœ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ์œผ๋ฉด ์—ฐ๊ฒฐ๋œ ๊ฐ™์€ ์ƒ‰ ๋ฟŒ์š”๋“ค์ด ํ•œ๊บผ๋ฒˆ์— ์—†์–ด์ง„๋‹ค. ์ด๋•Œ 1์—ฐ์‡„๊ฐ€ ์‹œ์ž‘๋œ๋‹ค. ๋ฟŒ์š”๋“ค์ด ์—†์–ด์ง€๊ณ  ๋‚˜์„œ ์œ„์— ๋‹ค๋ฅธ ๋ฟŒ์š”๋“ค์ด ์žˆ๋‹ค๋ฉด, ์—ญ์‹œ ์ค‘๋ ฅ์˜ ์˜ํ–ฅ์„ ๋ฐ›์•„ ์ฐจ๋ก€๋Œ€๋กœ ์•„๋ž˜๋กœ ๋–จ์–ด์ง€๊ฒŒ ๋œ๋‹ค. ์•„๋ž˜๋กœ ๋–จ์–ด์ง€๊ณ  ๋‚˜์„œ ๋‹ค์‹œ ๊ฐ™์€ ์ƒ‰์˜ ๋ฟŒ์š”๋“ค์ด 4๊ฐœ ์ด์ƒ ๋ชจ์ด๊ฒŒ ๋˜๋ฉด ๋˜ ํ„ฐ์ง€๊ฒŒ ๋˜๋Š”๋ฐ, ํ„ฐ์ง„ ํ›„ ๋ฟŒ์š”๋“ค์ด ๋‚ด๋ ค์˜ค๊ณ  ๋‹ค์‹œ ํ„ฐ์ง์„ ๋ฐ˜๋ณตํ•  ๋•Œ๋งˆ๋‹ค 1์—ฐ์‡„์”ฉ ๋Š˜์–ด๋‚œ๋‹ค. ํ„ฐ์งˆ ์ˆ˜ ์žˆ๋Š” ๋ฟŒ์š”๊ฐ€ ์—ฌ๋Ÿฌ ๊ทธ๋ฃน์ด ์žˆ๋‹ค๋ฉด ๋™์‹œ์— ํ„ฐ์ ธ์•ผ ํ•˜๊ณ  ์—ฌ๋Ÿฌ ๊ทธ๋ฃน์ด ํ„ฐ์ง€๋”๋ผ๋„ ํ•œ๋ฒˆ์˜ ์—ฐ์‡„๊ฐ€ ์ถ”๊ฐ€๋œ๋‹ค.

๋‚จ๊ทœ๋Š” ์ตœ๊ทผ ๋ฟŒ์š”๋ฟŒ์š” ๊ฒŒ์ž„์— ํ‘น ๋น ์กŒ๋‹ค. ์ด ๊ฒŒ์ž„์€ 1:1๋กœ ๋ถ™๋Š” ๋Œ€์ „๊ฒŒ์ž„์ด๋ผ ์ž˜ ์Œ“๋Š” ๊ฒƒ๋„ ์ค‘์š”ํ•˜์ง€๋งŒ, ์ƒ๋Œ€๋ฐฉ์ด ํ„ฐ๋œจ๋ฆฐ๋‹ค๋ฉด ์—ฐ์‡„๊ฐ€ ๋ช‡ ๋ฒˆ์ด ๋ ์ง€ ๋ฐ”๋กœ ํŒŒ์•…ํ•  ์ˆ˜ ์žˆ๋Š” ๋Šฅ๋ ฅ๋„ ํ•„์š”ํ•˜๋‹ค. ํ•˜์ง€๋งŒ ์•„์ง ์‹ค๋ ฅ์ด ๋ถ€์กฑํ•˜์—ฌ ๋‚จ๊ทœ๋Š” ์ž๊ธฐ ํ•„๋“œ์—๋งŒ ์‹ ๊ฒฝ ์“ฐ๊ธฐ ๋ฐ”์˜๋‹ค. ์ƒ๋Œ€๋ฐฉ์˜ ํ•„๋“œ๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ, ์—ฐ์‡„๊ฐ€ ๋ช‡ ๋ฒˆ ์—ฐ์†์œผ๋กœ ์ผ์–ด๋‚ ์ง€ ๊ณ„์‚ฐํ•˜์—ฌ ๋‚จ๊ทœ๋ฅผ ๋„์™€์ฃผ์ž!

์ž…๋ ฅ

  • ์ด 12๊ฐœ์˜ ์ค„์— ํ•„๋“œ์˜ ์ •๋ณด๊ฐ€ ์ฃผ์–ด์ง€๋ฉฐ, ๊ฐ ์ค„์—๋Š” 6๊ฐœ์˜ ๋ฌธ์ž๊ฐ€ ์žˆ๋‹ค. ์ด๋•Œ .์€ ๋นˆ๊ณต๊ฐ„์ด๊ณ  .์ด ์•„๋‹Œ๊ฒƒ์€ ๊ฐ๊ฐ์˜ ์ƒ‰๊น”์˜ ๋ฟŒ์š”๋ฅผ ๋‚˜ํƒ€๋‚ธ๋‹ค. R์€ ๋นจ๊ฐ•, G๋Š” ์ดˆ๋ก, B๋Š” ํŒŒ๋ž‘, P๋Š” ๋ณด๋ผ, Y๋Š” ๋…ธ๋ž‘์ด๋‹ค. ์ž…๋ ฅ์œผ๋กœ ์ฃผ์–ด์ง€๋Š” ํ•„๋“œ๋Š” ๋ฟŒ์š”๋“ค์ด ์ „๋ถ€ ์•„๋ž˜๋กœ ๋–จ์–ด์ง„ ๋’ค์˜ ์ƒํƒœ์ด๋‹ค. ์ฆ‰, ๋ฟŒ์š” ์•„๋ž˜์— ๋นˆ ์นธ์ด ์žˆ๋Š” ๊ฒฝ์šฐ๋Š” ์—†๋‹ค.

์ถœ๋ ฅ

  • ํ˜„์žฌ ์ฃผ์–ด์ง„ ์ƒํ™ฉ์—์„œ ๋ช‡์—ฐ์‡„๊ฐ€ ๋˜๋Š”์ง€ ์ถœ๋ ฅํ•œ๋‹ค. ํ•˜๋‚˜๋„ ํ„ฐ์ง€์ง€ ์•Š๋Š”๋‹ค๋ฉด 0์„ ์ถœ๋ ฅํ•œ๋‹ค.

๐Ÿ“ Logic

class Puyo { char[][] field = new char[12][6]; int[] x_ary = { -1, 0, 1, 0 }; int[] y_ary = { 0, 1, 0, -1 }; List<Pair> remove; Queue<Pair> queue; int[][] visited; ... }
  • ๋ฟŒ์š”์˜ ํ•„๋“œ๋ฅผ ๊ด€๋ฆฌํ•˜๊ธฐ ์œ„ํ•œ ํด๋ž˜์Šค๋ฅผ ์ƒ์„ฑํ•œ๋‹ค.
public boolean searchChains();
  • BFS๋ฐฉ์‹์œผ๋กœ ํ•„๋“œ์— ๋ฐœ์ƒ๊ฐ€๋Šฅํ•œ ์—ฐ์‡„๊ฐ€ ์žˆ๋Š”์ง€ ํƒ์ƒ‰ํ•œ๋‹ค.
  • ํ„ฐ์งˆ ์ˆ˜ ์žˆ๋Š” ๋ฟŒ์š”๋ฅผ List<Puyo> remove ์— ์ €์žฅํ•˜์—ฌ, ์—ฐ์‡„ ๋ฐœ์ƒ ์‹œ ํ•ด๋‹น ๋ฟŒ์š”๋“ค์„ ์ œ๊ฑฐํ•  ์ˆ˜ ์žˆ๊ฒŒ ํ•œ๋‹ค.
private void updateField();
  • ์—ฐ์‡„ ํƒ์ƒ‰ ์ดํ›„, ๋ฐœ์ƒํ•œ ์—ฐ์‡„๊ฐ€ ์žˆ๋Š” ๊ฒฝ์šฐ์—๋งŒ ํ•„๋“œ๋ฅผ ์—…๋ฐ์ดํŠธํ•˜๊ธฐ ์œ„ํ•ด ํ˜ธ์ถœ๋˜๋Š” ๋ฉ”์†Œ๋“œ์ด๋‹ค.

๐Ÿ“„ CODE

์ฝ”๋“œ ๋ณด๊ธฐ/์ ‘๊ธฐ๐Ÿ’ซ
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.List; import java.util.Queue; class Pair { int x; int y; Pair(int x, int y) { this.x = x; this.y = y; } } class Puyo { char[][] field = new char[12][6]; int[] x_ary = { -1, 0, 1, 0 }; int[] y_ary = { 0, 1, 0, -1 }; List<Pair> remove; Queue<Pair> queue; int[][] visited; public boolean searchChains() { remove = new LinkedList<>(); queue = new LinkedList<>(); visited = new int[12][6]; boolean pop = false; for (int i = 11; i >= 0; i--) { for (int j = 0; j < 6; j++) { if (field[i][j] == '.') continue; if (visited[i][j] != 0) continue; char now = field[i][j]; int cnt = 1; visited[i][j] = cnt++; queue.add(new Pair(i, j)); remove.add(new Pair(i, j)); while(!queue.isEmpty()) { Pair cur = queue.poll(); int curX = cur.x, curY = cur.y; for (int t = 0; t < 4; t++) { int ni = curX + x_ary[t], nj = curY + y_ary[t]; if (isBoundary(ni, nj)) continue; if (visited[ni][nj] > 0) continue; if (now == field[ni][nj]) { visited[ni][nj] = cnt++; queue.add(new Pair(ni, nj)); remove.add(new Pair(ni, nj)); } } } if (cnt >= 5) { pop = true; for (Pair p : remove) { field[p.x][p.y] = '.'; } } remove.clear(); } } if (pop) { updateField(); } return pop; } private void updateField() { for (int i = 0; i < 6; i++) { for (int j = 11; j > 0; j--) { if (field[j][i] == '.') { for (int k = j - 1; k >= 0; k--) { if (field[k][i] != '.') { field[j][i] = field[k][i]; field[k][i] = '.'; break; } } } } } } private boolean isBoundary(int x, int y) { return x < 0 | x > 11 | y < 0 | y > 5; } } public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String line; int chains = 0; Puyo puyo = new Puyo(); for (int i = 0; i < 12; i++) { line = br.readLine(); for (int j = 0; j < 6; j++) { puyo.field[i][j] = line.charAt(j); } } while(puyo.searchChains()) { chains++; } System.out.println(chains); br.close(); } }

โœ๏ธ Review

  • ์ฃผ์–ด์ง„ ์ƒํ™ฉ์—์„œ, ๋จผ์ € ์—ฐ์‡„๊ฐ€ ์ผ์–ด๋‚  ์ˆ˜ ์žˆ๋Š”์ง€ ํŒŒ์•…ํ•œ๋‹ค. ์—ฌ๋Ÿฌ ๊ฐœ์˜ ์—ฐ์‡„๊ฐ€ ๊ฐ€๋Šฅํ•˜๋‹ค๋ฉด, ์–ด๋А ์šฐ์„ ์ˆœ์œ„๋กœ ์—ฐ์‡„๋ฅผ ๋ฐœ์ƒ์‹œํ‚ฌ์ง€๋ฅผ ๊ณ ๋ฏผํ–ˆ๋‹ค.

    • ์ƒ๊ฐํ•ด๋ณด๋‹ˆ ์—ฐ์‡„๊ฐ„์˜ ์šฐ์„ ์ˆœ์œ„๋Š” ์ค‘์š”ํ•˜์ง€ ์•Š์•˜๊ณ , ์—ฐ์‡„ ๋ฐœ์ƒ ์ดํ›„ ํ•ด๋‹น ๋ฟŒ์š”๋“ค์„ ์–ด๋–ป๊ฒŒ ์ œ๊ฑฐํ•˜๋Š”๊ฐ€๊ฐ€ ๋” ์ค‘์š”ํ–ˆ๋‹ค.
  • ์—ฐ์‡„ ๋ฐœ์ƒ ๊ฐ€๋Šฅํ•œ ๋ฟŒ์š”๋“ค์„ ํƒ์ƒ‰๊ณผ ๋™์‹œ์— ์ œ๊ฑฐํ•  ๋ฐฉ๋ฒ•์ด ์—†๊ธฐ์— ๋ฆฌ์ŠคํŠธ์— ์ €์žฅํ•˜๋ฉด์„œ ์—ฐ์‡„๊ฐ€ ๋ฐœ์ƒํ•˜๋Š” ๊ฒฝ์šฐ์—๋งŒ ์ด๋ฅผ ์ œ๊ฑฐํ•˜๋Š” ๋ฐฉ์‹์„ ์ฐธ๊ณ ํ•˜์—ฌ ํ•ด๊ฒฐํ–ˆ๋‹ค.

๐Ÿ“• ์ถœ์ฒ˜

https://www.acmicpc.net/problem/11559

@Seongukbaek
๋ฐฐ์šฐ๊ณ  ์ •๋ฆฌํ•˜๊ณ  ๊ณต์œ ํ•˜๋Š” ๋Œ€ํ•™์ƒ ๋ฐฑ์„ฑ์šฑ์ž…๋‹ˆ๋‹ค ๐Ÿ˜€